/*
 * BinaryTrees.cpp
 *
 *  Created on: Apr 26, 2014
 *      Author: Anthony Varghese
 */

#include <iostream>
using std::cout;
using std::endl;
using std::ostream;

class Node{
public:
	Node(char c): data(c), left(nullptr), right(nullptr){
	}
	char data;
	Node* left;
	Node* right;
};

class BinaryTree{
public:
	BinaryTree(): root(nullptr){
	}
	BinaryTree(Node* r, BinaryTree& left, BinaryTree& right): root(r) {
		attachLeftSubtree( left );
		attachRightSubtree( right );
	}
	/*
	 * Copy constructor 1
	 */
	BinaryTree(Node* r) {
		deepcopy( root, r );
	}
	/*
	 * Copy constructor 2
	 */
	BinaryTree(const BinaryTree& source){
		deepcopy( root, source.root );
	}
	/*
	 * Assignment operator
	 */
	const BinaryTree& operator= (BinaryTree& rhs) {
        if (this != &rhs)
        	deepcopy(root, rhs.root);
        return *this;
    }
	~BinaryTree(){
		delete_postorder(root);
	}
	void attachLeftSubtree(BinaryTree& in){
		if (root->left != nullptr) {
			/*
			 * Delete existing left subtree
			 */
			delete_postorder( root->left );
		}
		/*
		 * Copy entire tree to be the new left subtree
		 */
		deepcopy( root->left, in.root);
	}
	void attachRightSubtree(BinaryTree& in){
		if (root->right != nullptr) {
			/*
			 * Delete existing right subtree
			 */
			delete_postorder( root->right );
		}
		/*
		 * Copy entire tree to be the new right subtree
		 */
		deepcopy( root->right, in.root);
	}
	BinaryTree detachLeftSubtree(){
		Node* temp = root->left;
		root->left = nullptr;
		return BinaryTree( temp );
	}
	BinaryTree detachRightSubtree(){
		Node* temp = root->right;
		root->right = nullptr;
		return BinaryTree( temp );
	}
	bool isEmpty() const {
		return (root == nullptr);
	}
	char rootItem() const {
		return root->data;
	}
	BinaryTree leftSubtree(){
		return BinaryTree( root->left );
	}
	BinaryTree rightSubtree(){
		return BinaryTree( root->right );
	}
	friend ostream& operator <<( ostream& o, BinaryTree& t){
		o << "Inorder traversal:   ";
		t.print_inorder(o, t.root);
		o << endl;
		return o;
	}

private:
	Node* root;

	void print_inorder(ostream& o, Node*t){
		if (t==nullptr) return;
		print_inorder(o, t->left);
		o << t->data << " ";
		print_inorder(o, t->right);
	}

	void delete_postorder(Node* t){
		if (t== nullptr) return;
		delete_postorder( t->left );
		t->left = nullptr;
		delete_postorder( t->right );
		t->right = nullptr;
		delete t;
	}

	void deepcopy(Node*& dest, Node* source){
		if (source == nullptr){
			dest = nullptr;
			return;
		} else {
			dest = new Node( source->data );
		}
		deepcopy( dest->left, source->left);
		deepcopy( dest->right, source->right);
	}
};


int main(){
	BinaryTree myTree( new Node( 'A') );
	BinaryTree b( new Node( 'B') );
	BinaryTree c( new Node( 'C') );
	BinaryTree d( new Node( 'D') );
	BinaryTree e( new Node( 'E') );
	BinaryTree f( new Node( 'F') );

	myTree.attachLeftSubtree( b );
	myTree.attachRightSubtree( c );

	cout << "myTree: " << myTree << endl;

	myTree.leftSubtree().attachLeftSubtree( d );

	cout << "myTree is now: " << myTree << endl;

	cout << "Done!";
}
